package leetcode_61_80;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class minWindow_76 {
    /**
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
     * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        /**
         * "ADOBECODEBANC",  "ABC"
         * "BANC"
         * 搞不来滑动窗口，就算搞出来最后也是繁琐的答辩
         * 官解如下，加上我的注释
         * 2ms 98%
         */
        int[] need = new int[128];//need[i]表示需要该元素的数量,0代表不需要, <0代表多余的数量
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        int i = 0, j = 0;// i 滑动窗口左端，j 右端
        int minSize = Integer.MAX_VALUE;//当前发现的满足要求的最小窗口长度
        int needCnt = t.length();//所需元素的总数量
        int start = 0;
        while(j < s.length()){
            //步骤一：不断增加 j 使滑动窗口增大，直到，needCnt==0 即窗口包含了T的所有元素
            char jChar = s.charAt(j);
            if(need[jChar] > 0){//新加入的字符是目前需要的元素
                needCnt--;
            }
            need[jChar]--;

            //此时窗口包含了T的所有元素，进入步骤二，处理窗口
            if(needCnt == 0){
                char iChar = s.charAt(i);
                while(need[iChar] < 0){   //扔掉窗口左端不需要的元素
                    //向右移动一格
                    need[iChar]++;
                    i++;
                    iChar = s.charAt(i);
                }
                if(j -i + 1 < minSize){  //窗口大小与最小窗口比较，更小就更新最小窗口
                    minSize = j-i+1;
                    start = i; //只有发现最小值时才更新start
                }
                //步骤三：让i再向右移动一个位置，使窗口不再满足条件，让其再次寻找，进入步骤一
                need[s.charAt(i)]++;
                i++;
                needCnt++;
            }
            j++;
        }
        return minSize == Integer.MAX_VALUE ? "" : s.substring(start, start+minSize);
    }
}
